package org.lql.algo.codecrush.hot100.linked;

import java.util.HashMap;
import java.util.Map;

/**
 * @author: liangqinglong
 * @date: 2025-10-06 15:51
 * @description: 146. LRU 缓存 <a href="https://leetcode.cn/problems/lru-cache/description/?envType=study-plan-v2&envId=top-100-liked">...</a>
 **/
public class LRUCache {

	class Node {
		int key;
		int val;
		Node prev;
		Node next;

		public Node() {
		}

		public Node(int key, int val) {
			this.key = key;
			this.val = val;
		}
	}

	private final int capacity;
	private final Map<Integer, Node> cache;
	private final Node head;
	private final Node tail;

		public LRUCache(int capacity) {
			this.capacity = capacity;
			this.cache = new HashMap<>();
			this.head = new Node();
			this.tail = new Node();
			head.next = tail;
			tail.prev = head;
		}

		public int get(int key) {
			if (cache.containsKey(key)) {
				Node node = cache.get(key);
				removeNode(node);
				insertNode(head, node);
				return node.val;
			} else {
				return -1;
			}
		}

		public void put(int key, int value) {
			if (cache.containsKey(key)) {
				Node node = cache.get(key);
				node.val = value;
				removeNode(node);
				insertNode(head, node);
			} else {
				Node node = new Node(key, value);
				cache.put(key, node);
				insertNode(head, node);
				if (cache.size() > capacity) {
					Node prev = tail.prev;
					cache.remove(prev.key);
					removeNode(prev);
				}
			}
		}

		public void insertNode(Node target, Node node) {
			node.prev = target;
			node.next = target.next;
			target.next.prev = node;
			target.next = node;
		}

		public void removeNode(Node node) {
			node.prev.next = node.next;
			node.next.prev = node.prev;
		}

	public static void main(String[] args) {
		LRUCache lruCache = new LRUCache(2);
		lruCache.put(1, 1);
		lruCache.put(2, 2);
		System.out.println(lruCache.get(1));
		lruCache.put(3, 3);
		System.out.println(lruCache.get(2));
		lruCache.put(4, 4);
		System.out.println(lruCache.get(1));
		System.out.println(lruCache.get(3));
		System.out.println(lruCache.get(4));
	}

}
